#
# @lc app=leetcode.cn id=460 lang=python3
#
# [460] LFU 缓存
#


# @lc code=start
class Node:
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.pre = None
        self.nxt = None
        self.frep = 0


def create_linked_list():
    head = Node()
    tail = Node()
    head.nxt = tail
    tail.pre = head
    return (head, tail)


class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.size = 0
        self.key_map = {}
        self.frep_map = {}
        self.min_frep = 0

    def get(self, key: int) -> int:
        if key in self.key_map:
            node = self.key_map[key]
            self.rise(node)
            return node.value
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.key_map:
            node = self.key_map[key]
            node.value = value
            self.rise(node)
        else:
            node = Node(key, value)
            self.key_map[key] = node
            self.rise(node)
            if self.size == self.capacity:
                del_node = self.frep_map[self.min_frep][1].pre
                del self.key_map[del_node.key]
                self.delete(del_node)
            else:
                self.size += 1
            self.min_frep = 1

    def delete(self, node):
        head, tail = self.frep_map[node.frep]
        if node.pre is head and node.nxt is tail:
            del self.frep_map[node.frep]
        else:
            node.pre.nxt = node.nxt
            node.nxt.pre = node.pre

    def add(self, node):
        head = self.frep_map[node.frep][0]
        node.pre = head
        node.nxt = head.nxt
        head.nxt.pre = node
        head.nxt = node

    def rise(self, node):
        if node.frep != 0:
            self.delete(node)
        node.frep += 1
        if node.frep not in self.frep_map:
            self.frep_map[node.frep] = create_linked_list()
        self.add(node)
        if self.min_frep == node.frep - 1 and self.min_frep not in self.frep_map:
            self.min_frep = node.frep


# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
# @lc code=end
